package arrays;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 *
 * 示例:
 *
 * 输入: [10,9,2,5,3,7,101,18]
 * 输出: 4
 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 * 说明:
 *
 * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
 * 你算法的时间复杂度应该为 O(n2) 。
 * 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class LengthOfLIS {

    public int lengthOfLIS(int[] nums) {

        if(nums == null || nums.length == 0){
            return 0;
        }
        int[] res = new int[nums.length];
        res[0] = 1;
        int max = 0;
        for(int i = 1; i < nums.length; i ++){
            int j = i - 1;
            res[i] = 1;
            while(j >= 0){
                if(nums[j] < nums[i]){
                    int count = res[j] + 1;
                    res[i] = Math.max(count, res[i]);
                    if(res[i] > max){
                        max = res[i];
                    }
                }
                j --;
            }
        }
        return max;
    }

    public int lengthOfLISII(int[] nums) {
        int[] tails = new int[nums.length];
        int res = 0;
        for(int num : nums) {
            int i = 0, j = res;
            while(i < j) {
                int m = (i + j) / 2;
                if(tails[m] < num) i = m + 1;
                else j = m;
            }
            tails[i] = num;
            if(res == j) res++;
        }
        return res;
    }

    public int lengthOfLISIII(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int[] list = new int[nums.length];
        int size = 0;
        for(int i = 0; i < nums.length; i ++){
            int l = 0;
            int r = size;
            while(l < r){
                int mid = l + (r - l)/2;
                if(list[mid] < nums[i]){
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            if(l == size){
                size ++;
            }
            list[l] = nums[i];
        }
        return size;
    }

    private int findToInsert(List<Integer> list, int target, int size){
        int l = 0;
        int r = size;
        while(l < r){
            int mid = l + (r - l)/2;
            if(list.get(mid) < target){
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if(l == size){
            size ++;
        }
        list.add(l, target);
        return size;
    }


    public static void main(String[] args){
        System.out.println((new LengthOfLIS()).lengthOfLISIII(new int[]{10,9,2,5,3,7,101,18,1,8,20,25,0,11,13,12,14,15}));
    }
}
